/*
 * @lc app=leetcode.cn id=491 lang=cpp
 *
 * [491] 非递减子序列
 *
 * https://leetcode.cn/problems/non-decreasing-subsequences/description/
 *
 * algorithms
 * Medium (51.84%)
 * Likes:    769
 * Dislikes: 0
 * Total Accepted:    166K
 * Total Submissions: 320.2K
 * Testcase Example:  '[4,6,7,7]'
 *
 * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * 
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [4,6,7,7]
 * 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [4,4,3,2,1]
 * 输出：[[4,4]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 15
 * -100 <= nums[i] <= 100
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    void BackTracking(vector<vector<int>>& result, vector<int>& path, 
        int startIndex, const vector<int>& nums) {
        if (path.size() >= 2)
            result.push_back(path);

        if (startIndex == nums.size())
            return;

        //在同层中使用 set 记录使用过的元素
        unordered_set<int> flag;

        for (int i = startIndex; i < nums.size(); i++) {
            //判断 是否使用重复元素 || 是否递增
            if ((flag.find(nums[i]) != flag.end()) ||
                (path.size() > 0 &&  nums[i] < path[path.size() - 1]))
                continue;

            flag.insert(nums[i]);    
            path.push_back(nums[i]);
            BackTracking(result, path, i + 1, nums);
            path.pop_back();

        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        //本题依旧需要去重, 需要在组合的基础上去重
        //但是和 90.子集II 和 40.组合总和II 不同, 本题不能够使用 bUsed 数组进行记录去重
        //本题需要求的是递增序列, 不能提前将数组进行排序

        //然而其实也很简单, 仍然是树层去重, 同层中不能使用重复数值的元素即可

        vector<vector<int>> result;
        vector<int> path;

        BackTracking(result, path, 0, nums);

        return result;
    }
};
// @lc code=end

